package two.chapter_3.c3_1;

import two.chapter_1.c1_3.CollectionEmptyException;

import java.util.HashMap;

public class RedBlackBST<Key extends Comparable<Key>, Value> implements SeqST<Key, Value> {
    private Node root;

    
    @Override
    public Key min() {
        return null;
    }

    @Override
    public Key max() {
        return null;
    }

    @Override
    public Key floor(Key key) {
        return null;
    }

    @Override
    public Key ceiling(Key key) {
        return null;
    }

    @Override
    public int rank(Key key) {
        return 0;
    }

    @Override
    public Key select(int k) {
        return null;
    }

    @Override
    public void deleteMin() {
        checkEmpty();
       /* if (!root.left.isRed() && !root.right.isRed()) {
            root.color = Node.COLOR_RED;
        }
        root = deleteMin(root);
        if (root != null) {
            root.color = Node.COLOR_BLACK;
        }*/
       if (!isRed(root.left) && !isRed(root.right)){
           root.color=Node.COLOR_RED;
       }
       root=deleteMin(root);
       if (root!=null){
           root.color=Node.COLOR_BLACK;
       }
    }




   /* private Node deleteMin(Node h) {
        if (h.left == null) {
            return null;
        }
        if (!h.left.isRed() && !h.left.left.isRed()) {//此时是h的left结点是一个2结点，需要将它扩展为3结点或4结点
            h = moveRedLeft(h);
        }
        h.left = deleteMin(h.left);
        return balance(h);
    }*/

    @Override
    public void deleteMax() {

    }

    @Override
    public int size(Key lo, Key hi) {
        return 0;
    }

    @Override
    public Iterable<Key> keys(Key lo, Key hi) {
        return null;
    }
    private Node deleteMin(Node h) {
        if (h.left==null){
            return null;
        }
        //确保左子结点不上2结点
        if (!isRed(h.left) &&!isRed(h.left.left)){
            //此时是2结点
            h=combineLeft(h);
        }
        h.left=deleteMin(h.left);
        return balance(h);
    }


    private Node combineLeft(Node h) {
        flipColors(h);
        if (isRed(h.right.left)){
            h.right=rotateRight(h.right);
            h=rotateLeft(h);
            flipColors(h);
        }
        return h;
    }

    @Override
    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = Node.COLOR_BLACK;
    }

    private Node put(Node node, Key key, Value value) {
        if (node == null) {
            return new Node(key, value);
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            node.right = put(node.right, key, value);
        } else if (cmp < 0) {
            node.left = put(node.left, key, value);
        } else {
            node.value = value;
        }
        //插入成功，检查结点颜色，做左旋、右旋、颜色变化操作
        if (node.left.isRed() && node.right.isRed()) {
            flipColors(node);
        }

        if (node.left.left != null && node.left.isRed() && node.left.left.isRed()) {
            node = rotateRight(node);
        }
        if (!node.left.isRed() && node.right.isRed()) {
            node = rotateLeft(node);
        }
        node.size = 1 + size(node.left) + size(node.right);
        return node;
    }


    @Override
    public Value get(Key key) {

        return get(root, key);
    }

    private Value get(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            return get(node.right, key);
        } else if (cmp < 0) {
            return get(node.left, key);
        } else
            return node.value;
    }

    @Override
    public void delete(Key key) {

    }

    @Override
    public boolean contains(Key key) {
        return get(key) != null;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public int size() {
        return size(root);
    }

    public int size(Node node) {
        if (node == null) {
            return 0;
        }
        return node.size;
    }


    @Override
    public Iterable<Key> keys() {
        return null;
    }

    private void checkEmpty() {
        if (isEmpty()) {
            throw new CollectionEmptyException();
        }
    }


    /********************************
     *           基本操作            *
     *           左右旋，颜色变换     *
     ********************************/
    private Node rotateLeft(Node node) {

        Node x = node.right;
        x.left = node;
        node.right = x.left;
        x.color = node.color;
        node.color = Node.COLOR_RED;
        x.size = node.size;
        node.size = 1 + size(node.left) + size(node.right);

        return node;
    }

    private Node rotateRight(Node node) {
        Node x = node.left;
        x.right = node;
        node.left = x.right;
        x.color = node.color;
        node.color = Node.COLOR_RED;
        x.size = node.size;
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }

    private void flipColors(Node h) {
       /* h.left.color=Node.COLOR_BLACK;
        h.right.color=Node.COLOR_BLACK;
        h.color=Node.COLOR_RED;*/

        // h must have opposite color of its two children
        // assert (h != null) && (h.left != null) && (h.right != null);
        // assert (!isRed(h) &&  isRed(h.left) &&  isRed(h.right))
        //    || (isRed(h)  && !isRed(h.left) && !isRed(h.right));
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
    }


    // Assuming that h is red and both h.left and h.left.left
    // are black, make h.left or one of its children red.
    private Node moveRedLeft(Node h) {
        // assert (h != null);
        // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);

        flipColors(h);
        if (isRed(h.right.left)) {
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
            flipColors(h);
        }
        return h;
    }

    // Assuming that h is red and both h.right and h.right.left
    // are black, make h.right or one of its children red.
    private Node moveRedRight(Node h) {
        // assert (h != null);
        // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
        flipColors(h);
        if (isRed(h.left.left)) {
            h = rotateRight(h);
            flipColors(h);
        }
        return h;
    }

    // restore red-black tree invariant
    private Node balance(Node h) {
        // assert (h != null);

        if (isRed(h.right)) h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);

        h.size = size(h.left) + size(h.right) + 1;
        return h;
    }

    private boolean isRed(Node node) {
        if (node == null) {
            return false;
        }
        return node.color == Node.COLOR_RED;
    }

    private class Node {
        Key key;
        Value value;
        Node left, right;
        int size;
        boolean color;
        static final boolean COLOR_RED = false;
        static final boolean COLOR_BLACK = true;

        /**
         * 新插入结点颜色为红色
         *
         * @param key
         * @param value
         */
        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            this.color = COLOR_RED;
            this.size = 1;
        }

        public boolean isRed() {
            return color == COLOR_RED;
        }
    }
}
